package 力扣.并查集;


public class 帮派的数目 {
/*    private int findGangNumber(int n, int[][] conn) {
        init(n);
        for (int i = 0; i < conn.length; i++) {
            Union(conn[i][0],conn[i][1]);
        }
        return  count;
    }
    private int[] F;
    private int count;
    private void init(int n){
        F = new int[n + 1];//这里因为人的编号从[1~N]，没有0,所以多开辟一个元素
        for (int i = 0; i <= n; i++) {
            F[i] = i;
        }
        count = n;
    }
    private int Find(int x){
        if (x == F[x]){
            return x;
        }
        return F[x] = Find(F[x]);
    }
    private void Union(int x,int y){
        if (Find(x) != Find(y)){
            count--;
        }
        F[Find(x)] = Find(y);
    }*/



    private int findGangNumber(int n, int[][] conn) {
        if (n == 0 || conn == null || conn.length == 0){
            return 0;
        }
        init(n);
        final int N  = conn.length;
        for (int i = 0; i < N; i++) {
            union(conn[i][0],conn[i][1]);
        }
        return count;

    }
    private int[] F;
    private int count;
    private void init(int n) {
        F = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {//各成一派
            F[i] = i;
        }
        count = n;
    }
    private void union(int x, int y) {
        if (Find(x) != Find(y)){//x,y的大哥不同
            F[Find(x)] = Find(y);//重新认大哥
            count--;
        }
    }
    private int Find(int x) {
        if (x == F[x]){
            return x;
        }
        return F[x] = Find(F[x]);
    }


}
